package SlidingWindow;

/**
 * @ClassName LC76
 * @Description 最小覆盖子串
 * @Author ZJX
 * @Date 2024/9/19 20:40
 * @Version 1.0
 */
public class LC76 {
    public String minWindow(String str, String target) {
        if (str.length() < target.length()) {
            return "";
        }

        // 记录 target 中每个字符的需求
        int[] tMap = new int[128];
        for (char c : target.toCharArray()) {
            tMap[c]++;
        }

        int left = 0, minLength = Integer.MAX_VALUE, start = 0, count = 0;
        int[] sMap = new int[128];

        for (int right = 0; right < str.length(); right++) {
            char rightChar = str.charAt(right);
            sMap[rightChar]++;

            // 如果当前字符是 target 需要的字符且窗口内该字符数量不超过需求，增加匹配数量
            if (tMap[rightChar] > 0 && sMap[rightChar] <= tMap[rightChar]) {
                count++;
            }

            // 当匹配字符数等于 target 字符串长度时，开始缩小窗口
            while (count == target.length()) {
                if (right - left + 1 < minLength) {
                    minLength = right - left + 1;
                    start = left;
                }

                char leftChar = str.charAt(left);
                sMap[leftChar]--;

                // 如果左边界的字符是 target 中需要的字符，且窗口中此字符数量小于需求，减少匹配数
                if (tMap[leftChar] > 0 && sMap[leftChar] < tMap[leftChar]) {
                    count--;
                }

                left++; // 缩小窗口
            }
        }

        return minLength == Integer.MAX_VALUE ? "" : str.substring(start, start + minLength);
    }
}
